package LeetCode._01算法入门.day12动态规划;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 挚爱之夕
 * @date 2022-03-03 - 03 - 03 - 21:56
 * @Description 给定一个三角形 triangle ，找出自顶向下的最小路径和。
 * 每一步只能移动到下一行中相邻的结点上。
 * 相邻的结点在这里指的是下标与上一层结点下标相同，或者等于上一层结点下标 + 1 的两个结点。
 * 也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
 * @Version 中等
 */
public class _120三角形最小路径和 {

    /*
    解释：如下面简图所示：
                   2
                  3 4
                 6 5 7
                4 1 8 3
    自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
     */

    static List<List<Integer>> triangle = new ArrayList<>();
    //by me 递归回溯（超时）
    @Test
    public void solve() {
        int res = minimumTotal(triangle);
        System.out.println(res);
    }

    int count = 0;
    int min = Integer.MAX_VALUE;
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0)
            return 0;
        if (triangle.size() == 1)
            return triangle.get(0).get(0);
        count = triangle.get(0).get(0);
        recursion(triangle, 1, 0);
        return min;
    }


    public void recursion(List<List<Integer>> triangle, int layer, int index) {
        if(layer == triangle.size()){
            min = Math.min(min, count);
            return;
        }
//        if(count > min)//不能剪枝
//            return;
        int temp = count;
        //下
        count += triangle.get(layer).get(index);
        recursion(triangle, layer + 1, index);
        //回溯
        count = temp;
        //下右
        count += triangle.get(layer).get(index + 1);
        recursion(triangle, layer + 1, index + 1);
        //回溯
        count = temp;
    }
    /*官方思路*/

    public int minimumTotal1(List<List<Integer>> triangle) {
        //层数
        int n = triangle.size();
        //辅助数组
        int[][] f = new int[n][n];
        f[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < n; ++i) {
            //最左侧只能从上面下来
            f[i][0] = f[i - 1][0] + triangle.get(i).get(0);
            //中间的可以从上面或左上角过来
            for (int j = 1; j < i; ++j) {
                f[i][j] = Math.min(f[i - 1][j - 1], f[i - 1][j]) + triangle.get(i).get(j);
            }
            //最右侧只能从左上角过来
            f[i][i] = f[i - 1][i - 1] + triangle.get(i).get(i);
        }
        //取最小的
        int minTotal = f[n - 1][0];
        for (int i = 1; i < n; ++i) {
            minTotal = Math.min(minTotal, f[n - 1][i]);
        }
        return minTotal;
    }

    static {
        List<Integer> list = new ArrayList<>();
        list.add(2);
        triangle.add(list);

        list = new ArrayList<>();
        list.add(3);
        list.add(4);
        triangle.add(list);

        list = new ArrayList<>();
        list.add(6);
        list.add(5);
        list.add(7);
        triangle.add(list);

        list = new ArrayList<>();
        list.add(4);
        list.add(1);
        list.add(8);
        list.add(3);
        triangle.add(list);
    }




    /*
    if (triangle == null || triangle.size() == 0)
            return 0;
        if (triangle.size() == 1)
            return triangle.get(0).get(0);

        int first = triangle.get(0).get(0); //上上层最优
        //记录上一层走的下标
        int index;
        //下面的元素
        Integer l = triangle.get(1).get(0);
        //下面的右边
        Integer r = triangle.get(1).get(1);
        int second = Math.min(l, r) + first; //上层最优
        if (l <= r) {
            index = 0;
        } else {
            index = 1;
        }
        List<Integer> line;
        for (int i = 2; i < triangle.size(); i++) {
            line = triangle.get(i);
            l = line.get(index);
            r = line.get(index + 1);

        }
     */
}
